package com.algrithom.bfs;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 1293. 网格中的最短路径
 * 
 * @author think
 */
public class Solution1 {
    
    private static final int MAX_RANGE = 40;
    
    private static final int MAX_DIRS = 4;
    
    public static void main(String[] args){
        // int[][] grid = new int[][] { { 0, 0, 0 }, { 1, 1, 0 }, { 0, 0, 0 }, { 0, 1, 1
        // }, { 0, 0, 0 } };
        int[][] grid = new int[][]{{0,0},{1,0},{1,0},{1,0},{1,0},{1,0},{0,0},{0,1},{0,1},{0,1},{0,0},{1,0},{1,0},{0,0}};

        Solution1 solution1 = new Solution1();
        System.out.println(solution1.shortestPath(grid,4));
        System.out.println(solution1.shortestPath2(grid,4));
    }
    
    public int shortestPath(int[][] grid,int k){
        int row = grid.length;
        int col = grid[0].length;
        if (validParam(k,row,col)) {
            return -1;
        }
        if (row == 1 && col == 1) {
            return 0;
        }

        k = Math.min(k,row + col - 2);
        // 到此节点的路径处理障碍总个数
        boolean[][][] visited = new boolean[row][col][k + 1];
        visited[0][0][0] = true;
        int[][] dirs = {{1,0},{0,1},{0,-1},{-1,0}};
        int stepCount = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0,0});
        while (!queue.isEmpty()) {
            int size = queue.size();
            stepCount++;
            for (int i = 0; i < size; i++) {
                int[] currentPoint = queue.poll();
                if (Objects.isNull(currentPoint)) {
                    continue;
                }
                for (int[] dir : dirs) {
                    int nextX = currentPoint[0] + dir[0];
                    int nextY = currentPoint[1] + dir[1];

                    if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                        continue;
                    }

                    if (nextX == row - 1 && nextY == col - 1) {
                        return stepCount;
                    }
                    if (grid[nextX][nextY] == 1 && currentPoint[2] >= k) {
                        continue;
                    }

                    int newBarrayCount = grid[nextX][nextY] == 1 ? currentPoint[2] + 1 : currentPoint[2];
                    if (visited[nextX][nextY][newBarrayCount]) {
                        continue;
                    }
                    visited[nextX][nextY][newBarrayCount] = true;
                    queue.offer(new int[]{nextX,nextY,newBarrayCount});
                }
            }
        }
        return -1;
    }
    
    private boolean validParam(int k,int m,int n){
        return m > 40 || m < 1 || n > 40 || n < 1 || k < 1 || k > m * n;
    }
    
    public int shortestPath2(int[][] grid,int k){
        int row = grid.length;
        int col = grid[0].length;
        if (validParam(k,row,col)) {
            return -1;
        }
        if (row == 1 && col == 1) {
            return 0;
        }

        int[][] visited = new int[row][col];
        for (int i = 0; i < row; i++) {
            Arrays.fill(visited[i],-1);
        }
        k = Math.min(k,row + col - 3);
        visited[0][0] = k;

        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        int stepCount = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0,0});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] currentPoint = queue.poll();
                if (Objects.isNull(currentPoint)) {
                    continue;
                }
                for (int[] dir : dirs) {
                    int nextX = currentPoint[0] + dir[0];
                    int nextY = currentPoint[1] + dir[1];

                    if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                        continue;
                    }

                    if (nextX == row - 1 && nextY == col - 1) {
                        return stepCount + 1;
                    }
                    if (grid[nextX][nextY] == 1 && currentPoint[2] >= k) {
                        continue;
                    }

                    int newBarrayCount = grid[nextX][nextY] == 1 ? currentPoint[2] + 1 : currentPoint[2];
                    // 需要预留更多的障碍数
                    if (visited[nextX][nextY] != -1 && visited[nextX][nextY] >= k - newBarrayCount) {
                        continue;
                    } else {
                        visited[nextX][nextY] = k - newBarrayCount;
                    }
                    queue.offer(new int[]{nextX,nextY,newBarrayCount});
                }
            }
            stepCount++;
        }
        return -1;
    }
}